package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-15 00:51
 */
public class Fib {

    int[] dp = null;
    public int fib(int n) {
        if (n<=1) return n;
        dp = new int[n + 1];
        dp[1] = dp[2] = 1;
        return dfs(n);
    }

    private int dfs(int n) {
        if (dp[n] > 0) return dp[n];
        dp[n]=dfs(n-1)+dfs(n-2);
        return dp[n];

    }

}
